COMMENT ⊗   VALID 00016 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	AM article for AI Handbook
C00004 00003	.chap(INTRODUCTION)
C00010 00004	.chap(THE TASK)
C00011 00005	. sec(Rationale)
C00016 00006	. sec(Plausible Reasoning in Mathematics)
C00024 00007	. sec(Discovery in Mathematics)
C00031 00008	.chap(|DESIGN OF THE ↓_AM_↓ PROGRAM|)
C00033 00009	. sec(Representation)
C00038 00010	. sec(Control)
C00052 00011	.chap(RESULTS)
C00053 00012	. sec(An Excerpt)
C00061 00013	. sec(AM as a Mathematician)
C00069 00014	. sec(|Limitations of ↓_AM_↓|)
C00075 00015	. sec(Conclusions about ↓_AM_↓)
C00079 00016	.chap(REFERENCES MENTIONED BY NUMBER IN THE TEXT)
C00096 ENDMK
C⊗;
AM article for AI Handbook


Written by Doug Lenat

First Draft: 11/27/78
Second Draft: 1/3/79



.chap(INTRODUCTION)

AM is a computer program, the thesis of Douglas Lenat, 
which explores elementary mathematics:
enlarges its vocabulary of objects and operators by defining new ones,
gathers empirical data about the concepts it posssesses, and makes
conjectures which connect some of those mathematical entities.  

The
design of AM is a blending of four powerful methodologies: heuristic
search, production systems, best-first search, and frames.
(i) AM is guided in its exploration by
over two hundred heuristics, which act like little plausible move
generators; they suggest new definitions and conjectures, and they
give hints as to how to gather more empirical data. (ii)  The obeying
of so many heeuristics is coordinated by representing each one as
a production rule (an expression of the form 
IF {some condition is satisfied} THEN {some appropriate plausible action}. 
The space that AM is exploring is so immense that some kind of chunking
is required, the granularity of operators like "conjoin two existing
definitions" is too fine. (iii)  The third idea woven into AM, that of
best-first search, enters in the form of an %bagenda%*, a job-list of
fairly large, meaningful tasks, each of which is plausible. The
tasks are at a much higher level, such as "generalize `Prime numbers'",
and each one is supported by a set of symbolic reasons. Together, the
reasons give an overall numeric rating to the task, which determines
its place on the agenda.  Only a small fraction of the tasks placed on the
agenda will ever be worked on: at each moment, AM expends its energy on
the best task, the one with the highest rating. (iv) Each concept is
represented as a frame, a structured entity with slots (Generalizations,
Examples, Definition, etc.) This enables tasks -- and heuristics --
to talk about a particular
slot of a particular concept.

The program began with a collection of one hundred concepts of finite set
theory and relations and data structures, and in a couple hours had 
defined about three hundred
new concepts, half of which were quite well-known ones in mathematics. One of
the synthesized concepts was equivalent to natural numbers.  AM rated this highly
and spent much time developing elementary number theory, including conjecturing
the fundamental theorem of arithmetic (each number has a 
unique prime factorization).  This is of course much better behavior than
one could expect from a blind sort of search through the space of legal
mathematical definitions and propositions. At any moment, AM could justify
its current efforts merely by printing out the symbolic reasons for the
top-rated task, the one it was working on. 

The significance of the project
lies both in the architecture of the program (a blend of three now-popular
methodologies) and in the fact that the program behaved well: an existence
proof that open-ended math research, theorem %bproposing%* not theorem
proving, could be adequately represented (and automated) as a heuristic search.
Finally, it is worth noting that the ultimate impediment to AM's progress
was its inability to discover new heuristic rules, as it discovered new
mathematical concepts. Only by constructing and experimenting with the program
were we thus able to learn where the next research thrust should be, along the
direction of automating the discovery and evaluation of heuristics.

.chap(THE TASK)

. sec(Rationale)

Few doubt the ubiquity of %binductive inference%*, but the archetypical
such enterprise is scientific research, and more specifically mathematics
research. To make that concrete:


1. In doing  math research, one  needn't cope with  the uncertainties  and
fallability of testing equipment; that  is, there are no uncertainties  in
the data  (compared  to, e.g.,  molecular  structure inference  from  mass
spectrograms).

2. Reliance  on  experts'  introspections  is one  of  the  most  powerful
techniques for codifying the judgmental criteria necessary to do effective
work in a field; by limiting the program to areas of mathematics in  which
the programmer  is competent,  he  needn't rely  on external  sources  for
guidance in  formulating such  heuristic rules.   Also, several  excellent
sources are available [13,14,15,21,22,25].

3. The more  formal a  science is,  the easier it  is to  automate. For  a
machine to carry out research  in psychology would require more  knowledge
about human information processing than  now is known, because  psychology
deals with entities as complex  as you and I.  Also, in a formal  science,
the %blanguages%* to communicate information can be simple even though the
%bmessages%* themselves be sophisticated.

4.   Since  mathematics  can  deal  with  any  conceivable  constructs,  a
researcher in that realm is not limited  to explaining observed data: he
can also %bcreate%*.  Related  to
this is the freedom  to investigate --  or to give up  on -- whatever  the
researcher wants to. There is no single discovery which is the "goal",  no
given problem to solve, no right or wrong behavior.

5. Unlike  "simpler" fields,  such  as propositional  logic, there  is  an
abundance of heuristic rules available for the picking.



The limitations  of math  as a  domain are  closely intertwined  with  its
advantages.  Having  no  ties  to  real-world data  can  be  viewed  as  a
limitation, as can having no clear  goal. There is always the danger  that
AM will give up on each theory  as soon as the first tough obstacle  crops
up.

. sec(Plausible Reasoning in Mathematics)

The inadequacy of formal  deductive methods in  mathematics has long  been
argued   [13,14,15],    often    lamented   in    the    conclusions    to
resolution-theorem-proving articles  [16,17].  An  early use  of  analogic
models in  geometry-theorem  proving  was  quite  successful  (Gelerneter's
[18] program "drew" a diagram meeting all the premises of the theorem,
and (among other things) presumed that segments or angles which turned out
to be equal were not so coincidentally; all such equalities could then
be drawn upon as lemmata).  Later
attempts at the introduction of heuristics into resolution theorem-provers
have been made by Bledsoe (in, e.g., non-standard analysis),
Pitrat (in propositional calculus), and a few others [16,19,22].   
It is  hypothesized that  the limited  successes  of
these schemes is due to the relatively small number of -- and variety  of
-- heuristics  they  possessed,  and  the fact  that  resolution  was  the
dominant driving force in each programi, using heuristics merely
to modulate the resolution search process.  The reason for the small number of
heuristics is simply the genuine paucity of informal rules of thumb  which
exist for the very  general environment in  which the vast majority of those 
programs  operate:
domain-independent (asemantic) predicate calculus theorem-proving.

Recently, Lenat has completed a thesis [3] about the mechanization of  the
"other  half"  of  mathematical  activity,  apart  from  proving:  namely,
defining new concepts and noticing plausible conjectures.  His  "AM"
system has no proof  capabilities, and this is one part of the AM model of
Mathematics Research:

.begin; spacing 0; preface 1; indent 0,3,0; group; once center; select b; preface 1;


1. The order in which a math textbook presents a theory is almost the
exact opposite  of the order in which  it was actually discovered and
developed.  In a text, new  definitions are stated with little or  no
motivation, and they turn out to be just the ones needed to state the
next big  theorem, whose proof then magically appears. In contrast, a
mathematician  doing   research  will   examine  some   already-known
concepts, perhaps trying to find some regularity in experimental data
involving them. The patterns he  notices are the conjectures he  must
investigate further, and these relationships directly motivate him to
make new definitions.

2.  Each step  the  researcher takes  while developing  a  new theory
involves choosing from  a large set of  "legal" alternatives --  that
is,  searching.   The  key to  keeping this  from  becoming a  blind,
explosive  search  is the  proper  use of  evaluation  criteria. Each
mathematician uses his own  personal heuristics to choose  the "best"
alternative available at each moment.

3.   Non-formal   criteria   (aesthetic  interestingness,   inductive
inference from  empirical evidence,  analogy, and  utility) are  much
more  important   than   formal  deductive   methods  in   developing
mathematically   worthwhile   theories,   and   in  avoiding   barren
diversions.

4. Progress in %bany%*  field of mathematics demands much  non-formal
heuristic  expertise  in  %bmany%*  different  "nearby"  mathematical
fields.  So a  broad, universal  core of  knowledge must  be mastered
before any single theory can meaningfully be developed.

5. It is sufficient (and  pragmatically necessary) to have and  use a
large  set  of  informal  heuristic  rules. These  rules  direct  the
researcher's next activities, depending  on the current situation  he
is  in.   These rules  can  be assumed  to  superimpose ideally:  the
combined  effect of several rules  is just the sum  of the individual
effects.

6. The  necessary  heuristic rules  are  virtually  the same  in  all
branches of mathematics,  and at all levels of  sophistication.  Each
specialized  field will  have some of  its own  heuristics; those are
normally much more powerful than the general-purpose heuristics.

7. For true understanding, the researcher should  grasp
(have access
to,  relate to,  store,  be able  to  manipulate, be  able to  answer
questions about)    each  concept  in  several  ways:  declaratively,
abstractly, operationally,  knowing  when it  is relevant,  and as  a
bunch of examples.

8. Common metaphysical  assumptions about nature and  science: Nature
is   fair,  uniform,  and   regular.     Coincidences  have  meaning.
Statistical considerations  are valid  when looking  at  mathematical
data.   Simplicity and  symmetry and  synergy are  the rule,  not the
exception.

.end; skip 2;

Let us try to motivate some of these assumptions, by elaborating
on how (in our view) mathematical discoveries are made.




. sec(Discovery in Mathematics);

Before  discussing  how  to  %bsynthesize%*  a  new  mathematical  theory,
consider briefly  how to  %banalyze%* one,  how to  construct a  plausible
chain of reasoning which stretches from a given discovery all the way back
to well-known concepts.

.subsec(Analysis of a Discovery);

One can rationalize a  given discovery by  working backwards, by  reducing
the creative  act to  simpler  and simpler  creative acts.   For  example,
consider the concept  of prime numbers.   How might one  be led to  define
such a notion,  if he'd never  heard of it  before?  Notice the  following
plausible strategy:

.ONCE spacing 0; INDENT 9,9,9 SELECT b;

"If f is a function which transforms elements of A into elements of B, and
B is ordered, then consider just those members of A which are  transformed
into ↓_extremal_↓ elements of B.  This set is an interesting subset of  A.
Name it and study it."

When f(x) means  "divisors of x",  and the ordering  is "by length",  this
heuristic says to consider  those numbers which have  a minimal number  of
factors -- that  is, the primes.   So this rule  actually %breduces%*  our
task from "proposing the concept of prime numbers" to two more  elementary
problems: "discovering ordering-by-length" and "inventing divisors-of".

But suppose we know this general rule: %b"If f is an interesting function,
consider its inverse."%* It reduces the task of discovering divisors-of to
the simpler  task of  discovering multiplication.   Eventually, this  task
reduces to  the  discovery  of  very  basic  notions,  like  substitution,
set-union, and equality.   To explain  how a given  researcher might  have
made a given  discovery, such  an analysis  must be  continued until  that
inductive task is  reduced to "discovering"  notions which the  researcher
already knew, which were his conceptual primitives.

.subsec(Syntheses of Discoveries)


Suppose  a  large  collection  of  these  heuristic  strategies  has  been
assembled (e.g., by analyzing a  great many discoveries, and writing  down
new heuristic  rules  whenever  necessary).   Instead  of  using  them  to
%bexplain%* how a given idea might have evolved, one can imagine  starting
from  a  basic  core  of   knowledge  and  "running"  the  heuristics   to
%bgenerate%* new  concepts.  We're  talking  about reversing  the  process
described in the last section: not how to %bexplain%* discoveries, but how
to %bmake%* them.

Notice that this forward  search is much  "bushier", much more  explosive,
than was the backwards analysis previously described.  So it's much harder
to actually make a  discovery than to rationalize  -- by hindsight --  how
one might  have  made  it.   We all  have  noticed  this  phenomenon,  the
"Why-didn't-I-think-of-that-sooner!!"  feeling.

The forward search is too explosive (see Combinatorial Explosion, in the
Search section of this handbook); we may hypothesize that the scientist
employs some kind of informal rules of thumb to constrain it. That is,  he
doesn't really follow  rules like  %b"Look at  the inverse  of each  known
function f"%*,  because that  would take  up too  much time.  Rather,  his
heuristic  rules   might  be   more   naturally  stated   as   productions
(condition/action rules)  like  this:  %b"If  f is  1-1  and  Range(f)  <<
Domain(f), Then look at f-inverse.%*" Henceforth, ↓_"%bheuristic rule%a"_↓
will mean a conditional rule of  thumb. In any particular situation,  some
subset of these rules will "trigger", and will suggest a manageable  space
of plausible  activities to  perform.  After  exploring that  space for  a
while, the situation  will have changed,  and the cycle  will begin  anew.
This double  layer of  heuristic  search shouldn't  bother anyone;  it  is
analogous to performing double induction instead of standard  mathematical
induction.

.chap(|DESIGN OF THE ↓_AM_↓ PROGRAM|);

Such syntheses are  precisely what  AM -- and  a scientist  -- does.   The
program consists of  a large  corpus of  primitive mathematical  concepts,
each  with  a  few  associated  heuristics.   Each  such  heuristic  is  a
situation/action  rule  which  functions   as  a  local  "plausible   move
generator".  Some suggest tasks for the system to carry out, some  suggest
ways of satisfying a given task, etc.  AM's activities all serve to expand
AM itself, to  enlarge upon a  given body of  mathematical knowledge.   AM
uses its heuristics  as judgmental  criteria to guide  development in  the
most promising direction.

. sec(Representation);

Each concept  is  represented  as  a frame-like  data  structure 
(unit, Being, schema, script,...)
with  25
different facets (slots, parts, aspects,...)  
The  types  of facets  include:  %bEXAMPLES,
DEFINITIONS, GENERALIZATIONS, DOMAIN/RANGE, ANALOGIES,  INTERESTINGNESS,%*
and many others.  Modular representation of concepts provides a convenient
scheme for organizing the heuristics; for example, the following  strategy
fits into the %bEXAMPLES%* facet of the %bPREDICATE%* concept:

.once indent 5,5,5; preface 1; spacing 0;

%b"If, empirically, 10 times  as many elements FAIL  some predicate P,  as
SATISFY it, then some ↓_generalization_↓ (weakened version) of P might  be
more interesting than P"%*.

AM considers this  suggestion after  trying to  fill in  examples of  each
predicate.   In   fact,   after   AM  attempts   to   find   examples   of
%bSET-EQUALITY%*, so  few are  found that  AM decides  to generalize  that
predicate.  The result is the creation  of several new predicates, one  of
which happens  to mean  "Has-the-same-length-as"  -- i.e.,  a  rudimentary
precursor to natural numbers.

Below is a typical concept, PRIMES, in  a state long after AM defined  and
explored it.

.begin nofill indent 0 preface 0

.group;
NAME: Prime Numbers 
DEFINITIONS: 
		ORIGIN: Number-of-divisors-of(x) = 2 
		PREDICATE-CALCULUS: Prime(x) ≡ (∀z)(z|x α→  z=1 α⊗ z=x) 
		ITERATIVE: (for x>1): For i from 2 to Sqrt(x), ¬(i|x) 

EXAMPLES: 2, 3, 5, 7, 11, 13, 17 
		BOUNDARY: 2, 3 
		BOUNDARY-FAILURES: 0, 1 
		FAILURES: 12 

GENERALIZATIONS: Nos., Nos. with an even no. of divisors, Nos. with a prime no. of divisors 

SPECIALIZATIONS: Odd Primes, Prime Pairs, Prime Uniquely-addables 

CONJECS: Unique factorization, Goldbach's conjecture, Extremes of Number-of-divisors-of 

INTU'S: %bA metaphor to the effect that Primes are the building blocks of all numbers%* 

ANALOGIES: 
		Maximally-divisible numbers are converse extremes of Number-of-divisors-of 
		Factor a non-simple group into simple groups 

INTEREST: Conjectures tying Primes to TIMES, to Divisors-of, to closely related operations 

WORTH: 800 

.apart; end; skip 2;

"Creating a  new  concept" is  a well-defined  activity: it  involves
setting  up a new  data structure like the one above,  and filling in
entries for some  of its facets  or slots.   Filling in a  particular
facet  of a  particular concept  is also  quite well-defined,  and is
accomplished  by executing a collection  of relevant heuristic rules.

. sec(Control);


AM is initially given a collection of  115 core concepts, with only a  few
facets filled in for each.  Its sole  activity is to choose some facet  of
some concept, and fill in that particular slot.  In so doing, new  notions
will often emerge.  Uninteresting  ones are forgotten, mildly  interesting
ones are kept as parts of one  facet of one concept, and very  interesting
ones are granted full concept-module status. Each of these new modules has
dozens of blank slots, hence the  space of possible actions (blank  facets
to fill in) grows rapidly.  The  same heuristics are used both to  suggest
new directions for investigation, and  to limit attention: both to  sprout
and to prune.



The fundamental kind of  task which AM performs,  its basic action, is  to
fill in a given  facet of a  given concept. To decide  which such task  to
work on  next, AM  maintains an  %bagenda%* of  tasks, a  global  job-list
ordered by priority.  A typical task is %b"Fill-in examples of  Primes"%*.
The agenda  may  contain  hundreds  of  entries  such  as  this  one.   AM
repeatedly selects the top task from the agenda and tries to carry it out.
This is the whole control structure! Of course, we must still explain  how
AM creates plausible  new tasks  to place on  the agenda,  how AM  decides
which task will be the best one to execute next, and how it carries out  a
task.

If  the  task  is  %b"Fill  in  new  Algorithms  for  Set-union"%*,   then
%bsatisfying%* it would  mean actually synthesizing  some new  procedures,
some new  LISP code  capable of  forming the  union of  any two  sets.   A
heuristic rule is %brelevant%* to a task iff executing that rule brings AM
closer to satisfying that task.  Relevance is determined a priori by where
the rule  is stored.  A rule  tacked onto  the Domain/range  facet of  the
Compose concept  would  be presumed  relevant  to the  task  %b"Check  the
Domain/range of Insert-o-Delete"%*.

Once a task  is chosen from  the agenda, AM  gathers some heuristic  rules
which might be relevant to satisfying  that task.  They are executed,  and
then AM picks  a new  task.  While  a rule  is executing,  three kinds  of
actions or effects can occur:


(i) Facets of some  concepts can get filled  in (e.g., examples of  primes
may actually be found and tacked onto the "Examples" facet of the "Primes"
concept).  A typical heuristic rule which might have this effect is:


%bTo fill in examples of X, where X is a kind of Y (for some more  general
concept Y),

Check the examples of Y; some of them may be examples of X as well.%*



For the task of  filling in examples  of Primes, this  rule would have  AM
notice that Primes is a  kind of Number, and  therefore look over all  the
known examples of  Number. Some  of those would  be primes,  and would  be
transferred to the Examples facet of Primes.

.skip 3

(ii) New concepts  may be  created (e.g.,  the concept  "primes which  are
uniquely representable as the sum of  two other primes" may be somehow  be
deemed worth studying).  A  typical heuristic rule  which might result  in
this new concept is:

%bIf some (but not most)  examples of X are also  examples of Y (for  some
concept Y),

Create a new concept  defined as the intersection  of those 2 concepts  (X
and Y).%*


Suppose AM has already isolated the concept of being representable as  the
sum of  two  primes  in only  one  way  (AM actually  calls  such  numbers
"Uniquely-prime-addable numbers").  When AM  notices that some primes  are
in this set, the above  rule will create a  brand new concept, defined  as
the set of numbers which are both prime and uniquely prime addable.

.skip 3

(iii) New tasks may be added to the agenda (e.g., the current activity may
suggest that the  following task  is worth  considering:  "Generalize  the
concept of prime  numbers").  A  typical heuristic rule  which might  have
this effect is:

%bIf very few examples of X are found,

Then add the following task to the agenda:  "Generalize the concept X".%*


Of course, AM contains a precise meaning for the phrase "very few".   When
AM looks for primes among examples  of already-known kinds of numbers,  it
will find dozens of non-examples for every example of a prime it uncovers.
"Very few"  is  thus naturally  implemented  as a  statistical  confidence
level.

.skip 3


The concept  of an  agenda is  certainly not  new:  schedulers  have  been
around for a long time.  But  one important feature of AM's agenda  scheme
%bis%* a new  idea:  attaching --  and using --  a list of  quasi-symbolic
reasons to each task which explain why the task is worth considering,  why
it's plausible.   %bIt is  the responsibility  of the  heuristic rules  to
include  reasons  for  any  tasks  they  propose.%*  For  example,   let's
reconsider the heuristic rule mentioned  in (iii) above.  It really  looks
more like the following:


%bIf very few examples of X are found,

Then add the following task to the agenda: "Generalize the concept X", for
the following reason:  "X's are  quite rare; a  slightly less  restrictive
concept might be more interesting".%*



If the same  task is  proposed by  several rules,  then several  different
reasons for it  may be present.   In addition, one  ephemeral reason  also
exists: "Focus of attention". Any tasks which are similar to the one  last
executed get "Focus of  attention" as a bonus  reason.  AM uses all  these
reasons, e.g.   to  decide how  to  rank the  tasks  on the  agenda.   The
"intelligence" AM exhibits is not so  much "what it does", but rather  the
%border%* in which  it arranges  its agenda.  For  example, alternating  a
randomly-chosen task and  the "best" task  (the one AM  chose to do)  only
slows the  system down  by a  factor of  2, yet  it totally  destroys  its
credibility as a rational researcher (as judged by the human user of  AM).
This is one conclusion of an experiment performed upon AM.

AM uses the list of reasons in another way: Once a task has been selected,
the quality of the reasons is used  to decide how much time and space  the
task will be permitted to  absorb, before AM quits and  moves on to a  new
task.


A crucial "heritability property" holds:  Any method for filling  in
facet f  of concept  C  will also  work  for filling  in  facet f  of  any
specialization  of  C.   Thus   when  the  task   "Fill  in  examples   of
%bSET-EQUALITY%*"   is   chosen,   AM   asks   each   generalization    of
%bSET-EQUALITY%* for help. Thus  it asks for ways  to fill in examples  of
any Predicate, any Activity, any Concept, and finally for ways to fill  in
examples of  Anything.  One  such  heuristic rule  known to  the  Activity
concept says: "Actually execute the activity on some random members of its
domain." Thus to fill in examples of %bSET-EQUALITY%*, its domain facet is
inspected, and AM sees it takes a  pair of objects as its arguments.  Then
AM accesses the Examples facet of the concept %bOBJECT%*, where it finds a
large list of objects. Obeying the  heuristic rule, AM repeatedly picks  a
pair of them  at random,  and sees  if they  satisfy %bSET-EQUALITY%*  (by
actually running  the LISP  function  stored in  the Algorithms  facet  of
%bSET-EQUALITY%*).  While  this  will  typically  return  False,  it  will
occasionally locate -- by random chance -- a pair of equal sets.

Other heuristics, tacked onto  other generalizations of  %bSET-EQUALITY%*,
provide additional methods  for executing  the task "Fill  in examples  of
%bSET-EQUALITY%*.  A heuristic stored on the concept %bANY-CONCEPT%*  says
to symbolically instantiate the  definition. A bag  of tricks is  provided
for this  purpose,  one  of  which ("instantiate  the  base  step  of  the
recursion")  works  nicely  on  the  recursive  definition  provided   for
%bSET-EQUALITY%*.  Notice that, as one might expect, the more general  the
concept is, the weaker (more time-consuming) its heuristics are.  For this
reason,  AM  consults  each  concept's   rules  in  order  of   increasing
generalization.

Executing a  task is  achieved by  locating relevant  rules of  thumb  and
evaluating them. 
The  location is  performed efficiently  because all  the
concepts are related by  generalization/specialization links, and  because
the above "heritability" property holds.

Notice the omnipresent reliance upon heuristic guidance.  They propose the tasks
(and associate reasons for them) for the agenda, they propose new concepts
to be defined, they discover (by search, synthesis, or analysis) entries
which can be put into specific acets of specific concepts.
There are even heuristics for naming new concepts (based on how they were
formed).

.chap(RESULTS);


. sec(An Excerpt)

To convey a bit of AM's flavor, we present a brief excerpt of it in action,
a bit of a trace of one of its runs.
After
reading through it, the  reader should be convinced  that AM is %bnot%*  a
theorem-prover, nor is it %brandomly%* manipulating entries in a knowledge
base, nor  is  it  %bexhaustively%*  manipulating  or  searching.   AM  is
carefully growing a network  of data structures representing  mathematical
concepts, by repeatedly using heuristics both (a) for guidance in choosing
a task to work on next, and  (b) to provide methods to satisfy the  chosen
task.


The following  points are  important but  can't be  conveyed by  any  lone
example:


(i) Although AM  appears to  have reasonable  natural language  abilities,
very little effort was expended in this area.

(ii) It is important to ask how general the program is:  is the  knowledge
base "just  right"  (i.e.,  finely  tuned to  elicit  this  one  chain  of
behaviors)?  The answer is "%bNo%*":  The whole point of this project  was
to show that  a relatively  small set of  general heuristics  can guide  a
nontrivial discovery process.  Each activity,  each task, was proposed  by
some heuristic rule (like  "look for extreme cases  of X") which was  used
time and time again,  in many situations.  It  was not considered fair  to
insert heuristic guidance which could only "guide" in a single  situation.
For example,  the same  heuristics which  lead AM  to decomposing  numbers
(using TIMES-inverse) and thereby  discovering unique factorization,  also
leads to decomposing numbers  (using ADD-inverse) and thereby  discovering
Goldbach's conjecture.



[[Back-slahes represent tabs; first tab at 5, then at around 20]]
[[Embolden the TASK nn lines]]
[[ALL of this was typed out by AM.  Even most of the concept names are
its own; the rest had been previously renamed by the user.]]

Now here is the excerpt itself.  A few of the lines have been anglicised
(e.g., the addition of "e.g."), and some of the concepts had previously
been renamed by the user (the human observor of the system). Otherwise,
this was just as AM typed it:

** ↓_TASK 65:_↓ **   Fill in Examples of the concept "Divisors-of".

\3 Reasons:\(1) No known examples of Divisors-of so far.
\\(2) TIMES, which is related to Divisors-of, is now very interesting.
\\(3) Focus of attention: AM recently defined Divisors-of.

26 examples found, in 9.2 seconds. e.g., Divisors-of(6)=α{1 2 3 6α}.


** ↓_TASK 66:_↓ **  Consider numbers having small sets of Divisors-of.

\2 Reasons:\(1) Worthwhile to look for extreme cases.
\\(2) Focus of attention: AM recently worked on Divisors-of.

Filling in examples of numbers with 0 divisors.
   0 examples found, in 4.0 seconds.
   Conjecture: no numbers have precisely 0 divisors.

Filling in examples of numbers with 1 divisors.
   1 examples found, in 4.0 seconds. e.g., Divisors-of(1) = α{1α}.
   Conjecture: 1 is the only number with precisely 1 divisor.

Filling in examples of numbers with 2 divisors.
   24 examples found, in 4.0 seconds. e.g., Divisors-of(13) = α{1 13α}.
   No obvious conjecture. May merit more study.
   Creating a new concept: "Numbers-with-2-divisors".

Filling in examples of numbers with 3 divisors.
   11 examples found, in 4.0 seconds. e.g., Divisors-of(49) = α{1 7 49α}.
   All numbers with 3 divisors are also Squares. Definitely merits more study.
   Creating a new concept: "Numbers-with-3-divisors".


** ↓_TASK 67:_↓ **  Consider the square-roots of Numbers-with-3-divisors.

\2 Reasons:\(1) Numbers-with-3-divisors are unexpectedly also Perfect Squares.
\\(2) Focus of attention: AM recently worked on Nos-with-3-divisors.

   All square-roots of Numbers-with-3-divisors seem to be Numbers-with-2-divisors.
        e.g.,  Divisors-of(Square-root(169)) = Divisors-of(13) = α{1 13α}.
   Even the converse of this seems empirically to be true.
        i.e.,  the square of each No-with-2-divisors seems to be a No-with-3-divisors.
        The chance of coincidence is below acceptable limits.
   Boosting the interestingness rating of each of the concepts involved.

[[italicise this next line]]
USER:  Rename Numbers-with-2-divisors as "Primes"


** ↓_TASK 68:_↓ **  Consider the squares of Numbers-with-3-divisors.

\3 Reasons:\(1) Squares of Numbers-with-2-divisors were interesting.
\\(2) Square-roots of Numbers-with-3-divisors were interesting.
\\(3) Focus of attention: AM recently worked on Nos-with-3-divisors.


. sec(AM as a Mathematician)

Now that we've  seen how  AM works,  and we've been  exposed to  a bit  of
"local" results,  let's take  a  moment to  discuss  the totality  of  the
mathematics  which  AM  carried   out.  All of this was done
by AM acting alone, with a human user watching it and occasionally
renaming some concepts for his or her own benefit.
 Like  a  contemporary   historian
summarizing the work of the Babylonian mathematicians, we shan't  hesitate
to use current terms and criticize by current standards.

AM began its investigations with  scanty knowledge of a few  set-theoretic
concepts.  Most of  the obvious  set-theory relations  (e.g., de  Morgan's
laws) were eventually uncovered; since AM never fully understood  abstract
algebra, the  statement  and  verification  of each  of  these  was  quite
obscure.  AM never  derived a formal  notion of infinity,  but it  naively
established conjectures like "a set can never be a member of itself",  and
procedures for making chains of new sets ("insert a set into itself").  No
sophisticated set theory (e.g., diagonalization) was ever done.

After this initial period of  exploration, AM decided that "equality"  was
worth generalizing, and  thereby discovered  the relation  "same-size-as".
"Natural numbers"  were based  on this,  and soon  most simple  arithmetic
operations were defined.

Since addition  arose as  an  analog to  union,  and multiplication  as  a
repeated substitution, it came  as quite a surprise  when AM noticed  that
they  were  related   (namely,  N+N  =   2xN).   AM  later   re-discovered
multiplication in three other ways:  as repeated addition, as the  numeric
analog of  the Cartesian  product of  sets, and using the cardinality of
the power set ofthe union of two sets.  

Raising to  fourth-powers, and  fourth-rooting,  were discovered  at  this
time.  Perfect  squares and  perfect  fourth-powers were  isolated.   Many
other numeric  operations  and  kinds  of numbers  were  found  to  be  of
interest:   Odds,  Evens,  Doubling,  Halving,  Integer-square-root,  etc.
Although it isolated the set of numbers  which had no square root, AM  was
never close to discovering rationals, let alone irrationals. No notion  of
"closure" was provided to -- or discovered by -- AM.


The associativity and  commutativity of multiplication  indicated that  it
could accept  a BAG  of numbers  as  its argument.   When AM  defined  the
inverse operation  corresponding  to  Times,  this  property  allowed  the
definition to be: "any bag of numbers (>1) whose product is x".  This  was
just the notion  of factoring  a number  x.  Minimally-factorable  numbers
turned out to be what  we call primes.  Maximally-factorable numbers  were
also thought to be interesting.

Prime pairs were discovered  in a bizarre way:  by restricting the  domain
and range of addition to primes (i.e., solutions of p+q=r in primes).


AM conjectured the fundamental theorem of arithmetic (unique factorization
into primes) and Goldbach's conjecture (every even number >2 is the sum of
two primes) in a surprisingly symmetric way.  The unary representation  of
numbers gave way to a representation as  a bag of primes (based on  unique
factorization), but AM never thought  of exponential notation.  Since  the
key concepts  of remainder,  greater-than,  gcd, and  exponentiation  were
never mastered, progress in number theory was arrested.

When a new base of %bgeometric%* concepts was added, AM began finding some
more general associations.   In place  of the strict  definitions for  the
equality of lines, angles, and triangles, came new definitions of concepts
we refer to as  Parallel, Equal-measure, Similar, Congruent,  Translation,
Rotation, plus many which  have no common name  (e.g. the relationship  of
two triangles sharing a common angle).  A cute geometric interpretation of
Goldbach's conjecture was  found [Given all  angles of a  prime number  of
degrees, (0,1,2,3,5,7,11,...,179 degrees),  then any angle  between 0  and
180 degrees can be approximated (to within 1 degree) as the sum of two  of
those angles.]   Lacking a  geometry "model"  (an analogic  representation
like the  one Gelernter  employed [18]),  AM was  doomed to  propose  many
implausible geometric conjectures.



. sec(|Limitations of ↓_AM_↓|);

Although  AM  fared  well  according  to  several  different  measures  of
performance, users of this handbook may utilize better knowledge of its
%blimitations%*.


As AM ran  longer and  longer, the concepts  it defined  were further  and
further from the primitives it began with, and the fficacy of its fixed set
of 250 heuristics gradually declined. 
The key deficiency was that of adequate %bmeta%*-rules[2,3,4]:  heuristics
which cause the creation and modification  of new heuristics. 
This lack would only be felt in a boot-strapping, open-ended task
environment such as math research.

Many concepts one  might consider "primitive"  are
missing from AM: proof, tricks for finding counterexamples, numbers,  etc.
Very few of  them are  ever discovered  by AM,  and even  those which  are
discovered will not have any powerful heuristics filled in for them.
The limitations of a too-small knowledge base can be overcome only by
investing the additional time to enlarge it.  With a learning system like AM,
one can spend a couple man-hours wrestling with each new concept, or let
the program squander probably much more of its time until it has discovered
and mastered that concept to the same level of proficiency.
It is a trade-off which almost always argues for the system-builder to
spend more time enlarging the knowledge base by hand.

Analogies in general were under-utilized. Specifically, analogies  between
heuristics were never even considered.  If one characterizes an analogy as
a  (partial)  correspondence  between  two  collections  of  objects   and
operators, then it is a small  conceptual step to imagine heuristic  rules
which look for and  develop such mappings: the  image of partial  matching
comes immediately  to mind.  AM possessed  a few  domain-independent  such
rules,  and  they  managed  to  produce  some  analogies  (e.g.,   between
multiplication   and    addition;   between    sets/union/same-size    and
numbers/add/equality), but the overall results  were quite meager in  this
area.


. sec(Conclusions about ↓_AM_↓);


The AM project stands as a living demonstration that a few hundred general
heuristic  rules  suffice  to  guide  a  searcher  --  an  automated  math
researcher -- as it  explores and expands a  large but incomplete base  of
math concepts.   AM  shows  that  creative  theoretical  research  can  be
effectively  modelled  as  heuristic  search,  just  as  Meta-Dendral  [1]
establishes a  similar hypothesis  for  the more  constrained,  real-world
field of mass spectroscopy.

AM's design combined four now-popular themes: modular representation of knowledge,
distributed control via production rules, reliance upon heuristics acting
as plausible-move generators, and best-first searching via an agenda scheduler.
AM introduced (1975) that control structure  based upon an  agenda of  small
plausible research tasks, each with a list of supporting reasons attached.

The main successes were the few novel  ideas it came up with [including  a
new result in  number theory,  dealing with numbers  having very  ↓_many_↓
divisors], the ease with which  new domains were discovered [e.g.,  number
theory] or  introduced  by  hand  [plane  geometry],  and  the  apparently
rational sequences of behavior AM exhibited.

The continuation of this line of research by Lenat is the Eurisko program.
The hypothesis  that  has been  added  is that  the  meta-level  knowledge
required to synthesize and reason about heuristics is a %bsubset%* of  the
knowledge already in AM about  synthesizing and reasoning about  concepts.
That is, Eurisko's meta-rules  are merely some of  the very general  rules
that AM already had.  The only real change, then, from AM to Eurisko is to
re-represent (recode) each  heuristic from Lisp  code into a  full-fledged
concept with facets.  The heuristics, which deal with facets of  concepts,
will then be capable of dealing  with each other.  This work is  currently
in progress at Stanford University.

Future AM-like programs may serve as assistants to scientists and
engineers, synergetically
collaborating with them in the conception, planning, and execution of
their research and development activities.

.chap(REFERENCES MENTIONED BY NUMBER IN THE TEXT)

[[the backslash is the tab character for PUB]]

.begin fill; indent 0,4,0; tabs 5; turn on "\"; spacing 0; preface 1;

[1]\Bruce  G.  Buchanan,  %bApplications  of  Artificial  Intelligence  to
Scientific Reasoning%*, Second USA-Japan Computer Conference, published by
AFIPS and IPSJ, Tokyo, 1975, pp. 189-194.

[2]\Randall  Davis,  %bApplications  of   Meta  Level  Knowledge  to   the
Construction, Maintenance,  and  Use  of  Large  Knowledge  Bases%*,  SAIL
AIM-271, Artificial  Intelligence Laboratory,  Stanford University,  July,
1976.


[3]\Douglas  B.  Lenat,  %bAM:  An  Artificial  Intelligence  Approach  to
Discovery in Mathematics as  Heuristic Search%*, SAIL AIM-286,  Artificial
Intelligence Laboratory, Stanford University, July, 1976.  Jointly  issued
as Computer Science Dept. Report No. STAN-CS-76-570.

[4]\R. D. Laing, "%bRules  and Metarules%*", in  uu-%bThe Politics of  the
Family and Other Essays%*], Vintage Books, N.Y., 1971, pp. 103-116.

[5]\Herbert Simon and  Kenneth Kotovsky, %bHuman  Acquisition of  Concepts
for Sequential Patterns%*,  Psychology Review 70,  No. 6, November,  1963,
pp. 534-546.


[6]\Malcolm Pivar  and  Mark  Finkelstein, %bAutomation,  using  LISP,  of
Inductive Inference on Sequences%*, in (Berkeley and Bobrow, eds.)  uu-The
Programming Language LISP:  Its Operation  and Applications],  Information
International, Cambridge, Mass., March, 1964.


[7]\C.  G.  Hempel,  %bFundamentals  of  Concept  Formation  in  Empirical
Science%*, University of Chicago Press, Chicago, 1952.

[8]\Patrick  H.   Winston,   %bLearning   Structural   Descriptions   from
Examples%*, EE TR-76, Project MAC TR-231, MIT AI Lab, September, 1970.

[9]\Herbert Simon, %bDoes Scientific Discovery Have a Logic?%*, Philosophy
of Science, 40, No. 4, December, 1973, pp. 471-480.

[10]\Marvin Minsky, %bFrames%*, in (P. Winston, ed.)  uu-The Psychology of
Computer Vision], McGraw Hill, N.Y. 1975.



[11]\Edward  A.  Feigenbaum,  Bruce   Buchanan,  Joshua  Lederberg,   %bOn
Generality and Problem Solving: A Case Study Using the DENDRAL  Program%*,
in (Meltzer and Michie, eds.) Machine Intelligence 6, 1971, pp. 165-190.

[12]\Inductive determination  of the  structure of  proteins by  automatic
processing of  electron  density X-ray  crystollographic  data.  (informal
communications with Dr.  Robert Engelmore and  Prof. Edward Feigenbaum  of
Stanford University.)


[13]\Henri  Poincare',   %bThe  Foundations   of  Science:   Science   and
Hypothesis, The Value of Science, Science and Method%*, The Science Press,
N.Y. 1929.

[14]\G. Polya,  %bMathematics and  Plausible Reasoning%*,  John Wiley  and
Sons, N.Y., (2 vols.) 1954.

[15]\Imre Lakatos,  %bProofs and  Refutations: The  Logic of  Mathematical
Discovery%*, Cambridge U. Press, London, 1976.

[16]\Woody W. Bledsoe, %bSplitting  and Reduction Heuristics in  Automatic
Theorem Proving%*, Artificial Intelligence 2, 1971, p. 73.

[17]\H. Wang,  %bToward Mechanical  Mathematics%*,  IBM J.   Research  and
Development 4, No. 1, January, 1960, pp. 2-22.

[18]\H. Gelernter, %bRealization of a Geometry-Theorem Proving  Machine%*,
in (Feigenbaum and Feldman, eds.) uu-Computers and Thought], McGraw  Hill,
N.Y., 1963, pp. 134-152.

[19]\Robert Kling, %bReasoning by  Analogy with Applications to  Heuristic
Probllem Solving: A Case  Study%*, Memo AIM-147,  CS Dept. Report  CS-216,
Stanford U., August, 1971.

[20]\T.  Evans,  %bA  Program   for  the  Solution  of   Geometric-Analogy
Intelligence Test Questions%*,  in (Minsky,  ed.) uu-Semantic  Information
Processing]. MIT Press, Cambridge, Mass., 1968, pp. 271-353.

[21]\Donald Knuth,  %bSurreal  Numbers%*,  Addison-Wesley,  Reading,Mass.,
1974.


[22]\D.  Brotz,  %bEmbedding  Heuristic  Problem  Solving  Methods  in   a
Mechanical Theorem Prover%*,  Stanford University  Computer Science  Dept.
Report No. STAN-CS-74-443, August, 1974.

[23]\Arthur Koestler, %bThe Act of Creation%*, Dell Pub., N.Y., 1967.

[24]\Seymour Papert,  %bTeaching  Children  to  be  Mathematicians  Versus
Teaching About Mathematics%*, Intl. J. Math Ed. Sci. Technology 3, No.  3,
July-Sept., 1972, pp. 249-262.

[25]\Jaques Hadamard, %bThe  Psychology of Invention  in the  Mathematical
Field%*, Dover Pub., N.Y., 1945.

.end